package problem45;

//45.跳跃游戏2
//https://leetcode.cn/problems/jump-game-ii/description/

class Solution1 {
    public static int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i = 1; i<n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for(int j = 0; j<i; j++) {
                if(j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[n-1]-1;
    }
}

/**
 dp[i]:到达第i个位置所需的最短步数

 */